package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/9 8:40
 */
public class C154 {

    // https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
    public static int findMin(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }

    // 半个暴力法
    public static int findMin2(int[] nums) {
        int k = 0;
        for (; k + 1 < nums.length && nums[k + 1] >= nums[k]; k++) {
        }
        k++;
        return k < nums.length ? nums[k] : nums[0];
    }


    // 二分
    public static int findMin3(int[] nums) {
        int l = 0, r = nums.length - 1, m;
        while (l < r) {
            m = l + ((r - l) >> 1);
            if (nums[m] < nums[r]) {
                r = m;
            } else if (nums[m] > nums[r]) {
                l = m + 1;
            } else {
                // 因为有相等元素, 所以放弃右边还有中间那个数兜底呢
                r--;
            }
        }
        return nums[l];
    }

    // for test
    public static void main(String[] args) {
        int[] nums = {1, 1};
        System.out.println(findMin(nums));
        System.out.println(findMin2(nums));
        System.out.println(findMin3(nums));
    }

}
